Muhammad Haris Rao
Throughout, we define functions $\chi_P : \mathbb{Z}_{>0} \longrightarrow \{ 0 , 1 \}$ and $\pi : \mathbb{R}_{\ge 0} \longrightarrow \mathbb{R}$ by \begin{align*} \chi_P(n) &= \begin{cases} 1 &\text{ , if $n$ is prime} \\ 0 &\text{ , if $n$ is not prime} \end{cases} \\ \pi(x) &= \sum_{n \le x} \chi_P(n) \\ \vartheta (x) &= \sum_{n \le x} \chi_P(n) \log{n} \end{align*} Evidently, $\pi$ is the famous prime counting function which states the number of prime integers bounded above by a given real argument. The celebrated prime number theorem is the following result:
Theorem (Prime Number Theorem): The number of primes bounded by a real value $x$ is assympotitcally equivalent to $x / \log{x}$. That is, \begin{align*} \lim_{x \to \infty} \frac{\pi(x)}{x / \log{x}} = 1 \end{align*}
The full proof of this theorem was completed in 1896, simultaneously discovered by Simon de la Valé Poussin and Jacques Hadamard, both heavy on techniques from complex anlaysis. Pafnuty Lvovich Chebyshev (1821 - 1894) was also someone who long attempted a proof of this. However, he was unsuccessful, and never lived to see the full proof. Here, we will follow Chebychev's proof that $x / \log{x}$ is the exact order of growth of $\pi(x)$.
First, to recall techniques and lemmas which will be used in the proofs. A classic result in analytic number theory used to convert between discrete sums and integrals is the Abel summation formula:
Theorem (Abel Summation): Fix real numbers $0 \le x \le y$. Let $f : [a, b] \to \mathbb{R}$ bo continuous on its domain and continuously differentiable on $(a, b)$, and let $g : \mathbb{Z}_{> 0} \to \mathbb{R}$ be an arithmetic function. Then for any $0 \le x \le y$, we have \begin{align*} \sum_{x < n \le y} f(n) g(n) &= f(y) \sum_{n \le y} g(n) - f(x) \sum_{n \le x} g(x) - \int_x^y f^\prime(t) \sum_{n \le t} g(n) \, dt \end{align*}
The proof for this will be omitted, as it can be found in any book on analytic number theory, and many texts on real analysis. If one thinks of summation as integration, then the above formula has the same form as integration by parts.
We can use this result to prove the following:
Theorem: The prime counting function can be written as \begin{align*} \pi(x) &= \frac{\vartheta(x)}{\log{x}} + \int_2^x \frac{\vartheta(t)}{t \log^2{t}} \, dt \end{align*}
Proof. This follows directly from the Abel summation formula: \begin{align*} \pi(x) &= 1 + \sum_{2 < n \le x} \frac{\chi_P(n) \log{n}}{\log{n}} \\ &= 1 + \frac{1}{\log{x}} \sum_{n \le x} \chi_P(n) \log{n} - \frac{1}{\log{2}} \sum_{n \le 2} \chi_P(n) \log{n} + \int_2^x \frac{1}{t \log^2{t}} \left( \sum_{n \le t} \chi_P(n) \log{n} \right) \, dt \\ &= \frac{\vartheta(x)}{\log{x}} + \int_2^x \frac{\vartheta(t)}{t \log^2{t}} \, dt \\ \end{align*}
Another result we will need is Legendre's identity. For this, we define for each prime $p$ function $\nu_p : \mathbb{Z}_{> 0} \longrightarrow \mathbb{Z}_{\ge 0}$ by $\nu_p(n)$ being the multiplicity of $p$ in the prime factorisation of $n$. That is, \begin{align*} n &= \prod_{p \ge 1} p^{\nu_p(n)} \end{align*} Legendre's identity is
Theorem (Legendre's Identity): For all $n \in \mathbb{Z}_{> 0}$ and any prime $p$, it holds that \begin{align*} \nu_p \left( n! \right) &= \sum_{\alpha \ge 1} \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor \end{align*}
Proof. It is clear that $\nu_p(ab) = \nu_p(a) + \nu_p(b)$ for all $a, b \in \mathbb{Z}_{> 0}$. Thus, \begin{align*} \nu_p\left( n! \right) &= \sum_{k = 1}^n \nu_p(k) = \sum_{\alpha \ge 0} \alpha \left( \#\left\{ k \in \{ 1, 2, \cdots, n \} \mid \nu_p(k) = \alpha \right\} \right) \end{align*} Instead of counting over the integers $1, 2, \cdots, n$, we will count over the values which $\nu_p$ takes. We simply need to count how may times a prime $p$ will occur in all the numbers $1, 2, \cdots, n$ (counting with multiplicity). Clearly, there is a bijection between the positive interes less than $n$ which $p$ has multiplicity $p^\alpha$ and the positive integers less than $n / p^\alpha$ which are not divisible by $p$. Therefore, the amount of integers at most $n$ in which $p$ has multiplicity $\alpha$ would be \begin{align*} \#\left\{ k \in \{ 1, 2, \cdots, n \} \mid \nu_p(k) = \alpha \right\} = \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor - \bigg\lfloor \frac{n}{p^{\alpha + 1}} \bigg\rfloor \end{align*} Then the desired result is \begin{align*} \nu_p \left( n! \right) &= \sum_{\alpha \ge 1} \alpha \left( \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor - \bigg\lfloor \frac{n}{p^{\alpha + 1}} \bigg\rfloor \right) \\ &= \sum_{\alpha \ge 1} \alpha \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor - \sum_{\alpha \ge 1} \alpha \bigg\lfloor \frac{n}{p^{\alpha + 1}} \bigg\rfloor \\ &= \sum_{\alpha \ge 1} \alpha \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor - \sum_{\alpha \ge 2} (\alpha - 1) \bigg\lfloor \frac{n}{p^{\alpha}} \bigg\rfloor \\ &= \sum_{\alpha \ge 1} \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor \end{align*}
The above theorem yields \begin{align*} \log{n!} &= \log{ \prod_{p \ge 1} p^{\nu_p(n!)}} = \sum_{p \ge 1} \nu_p(n!) \log{p} = \sum_{p \le n} \log{p} \sum_{\alpha \ge 1} \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor \end{align*}
Finally, we require the following elementary inequality:
Lemma: For all non-negative integers $n \ge 1$, \begin{align*} 2^n \le { 2n \choose n } \le 4^n \end{align*}
Proof. This is a simple induction. The result is true for $n = 1$ clearly, and if it is true for any $n$, then \begin{align*} { 2(n + 1) \choose n + 1 } &= \frac{(2n + 2)!}{(n + 1)!(n + 1)!} = \frac{(2n + 1)(2n + 2)}{(n + 1)^2} \frac{(2n)!}{n! n!} \le \frac{(2n + 2)^2}{(n + 1)^2} 4^n = 4^{n + 1} \end{align*} and likewise, \begin{align*} { 2(n + 1) \choose n + 1 } &= \frac{(2n + 2)!}{(n + 1)!(n + 1)!} = \frac{(2n + 1)(2n + 2)}{(n + 1)^2} \frac{(2n)!}{n! n!} \ge \frac{(2n + 1)(2n + 2)}{(n + 1)^2} 2^n = \frac{2n + 1}{n + 1} 2^{n + 1} \ge 2^{n + 1} \end{align*} By the principle of induction, the desired result follows.
We now all have the necessities to prove Cehbychev's bounds:
Theorem: There exist positive real numbers $A < B$ such that \begin{align*} A \frac{x}{\log{x}} \le \pi(x) \le B \frac{x}{\log{x}} \end{align*} for all $x \ge 2$.
Proof. We have \begin{align*} \log { 2n \choose n } &= \log{(2n)!} - 2 \log{n!} \\ &= \sum_{p \le 2n} \log{p} \sum_{\alpha \ge 1} \bigg\lfloor \frac{2n}{p^\alpha} \bigg\rfloor - 2\sum_{p \le n} \log{p} \sum_{\alpha \ge 1} \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor \\ &= \sum_{n < p \le 2n} \log{p} \sum_{\alpha \ge 1} \bigg\lfloor \frac{2n}{p^\alpha} \bigg\rfloor + \sum_{p \le n} \log{p} \sum_{\alpha \ge 1} \left( \bigg\lfloor \frac{2n}{p^\alpha} \bigg\rfloor - 2 \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor \right) \end{align*} It is true for all $ x \ge 0$ that $\lfloor 2x \rfloor - 2 \lfloor x \rfloor \in \{ 0, 1 \}$. Then we have \begin{align*} n \log{4} &= \log{4^n} \ge \log { 2n \choose n } \ge \sum_{n < p \le 2n} \log{p} \sum_{\alpha \ge 1} \bigg\lfloor \frac{2n}{p^\alpha} \bigg\rfloor \end{align*} Since $p > n$, it holds that $\lfloor 2n / p^\alpha \rfloor \le 1$. Also, if $\alpha \ge 2$, then \begin{align*} p^\alpha \ge p^2 \ge (n + 1)^2 = n^2 + 2n + 1 > 2n \end{align*} So $\lfloor 2n / p^\alpha \rfloor = 0$ when $\alpha \ge 2$, and $\lfloor 2n / p^\alpha \rfloor = 1$ when $\alpha = 1$. Hence, \begin{align*} n \log{4} &\ge \sum_{n < p \le 2n} \log{p} = \vartheta(2n) - \vartheta(n) \end{align*} We can write $\vartheta(n)$ as a telescoping series and use this bound \begin{align*} \vartheta(n) &= \sum_{k \ge 0} \left( \vartheta\left( n / 2^k \right) - \vartheta\left( n / 2^{k + 1} \right) \right) \le \sum_{k \ge 0} \frac{n\log{4}}{2^{k + 1}} = n \log{4} \end{align*} This relation also holds for non-integer arguments. Indeed, \begin{align*} \vartheta\left( x \right) &= \vartheta \left( \lfloor x \rfloor \right) \le \lfloor x \rfloor \log{4} \le x \log{4} \end{align*} From the representation of $\pi(x)$ obtained using the Abel summation formula, we have \begin{align*} \pi(x) &= \frac{\vartheta(x)}{\log{x}} + \int_2^x \frac{\vartheta(t)}{t \log^2{t}} \, dt \le \frac{x\log{4} }{\log{x}} + \log{4} \int_2^x \frac{1}{\log^2{t}} \, dt \end{align*} The integral may be bounded as follows for $x \ge 4$: \begin{align*} \int_2^x \frac{1}{\log^2{t}} \, dt &= \int_2^{\sqrt{x}} \frac{1}{\log^2{t}} \, dt + \int_{\sqrt{x}}^x \frac{1}{\log^2{t}} \, dt \\ &\le \frac{\sqrt{x} - 2}{\log^2{2}} + \frac{x - \sqrt{x}}{\log^2{\sqrt{x}}} \\ &\le \frac{x}{\sqrt{x}\log^2{2}} + \frac{x}{\log{\sqrt{x}}} \\ &\le \left( 2 + \frac{1}{\log^2{2}} \right) \frac{x}{\log{x}} \end{align*} So we have overall \begin{align*} \pi(x) \le \left( 3 \log{4} + \frac{2}{\log{2}} \right) \frac{x}{\log{x}} \end{align*} It is easily checked that the above quantitiy if always strictly greater than 1. Since 1 bounds $\pi(x)$ from above for all $x < 4$, the above inqequality actually holds for all $x \ge 2$.
Now to compute a lower bound. We begin with \begin{align*} n \log{2} \le \log { 2n \choose n } = \sum_{p \le 2n} \log{p} \sum_{\alpha \ge 1} \left( \bigg\lfloor \frac{2n}{p^\alpha} \bigg\rfloor - 2 \bigg\lfloor \frac{n}{p^\alpha} \bigg\rfloor \right) \end{align*} Recall that the expression inside the innder summation is always either $0$ or $1$. We bound above by taking it to be 1 for $\alpha \le \log_p{2n}$ and 0 otherwise: \begin{align*} n \log{2} \le \sum_{p \le 2n} \log{p} \sum_{\alpha = 1}^{\log_p{2n}} 1 = \sum_{p \le 2n} \log{p} \log_p{2n} = \pi \left( 2n \right) \log{2n} \end{align*} Hence, \begin{align*} \frac{\log{2}}{2} \frac{2n}{\log{2n}} \le \pi(2n) \end{align*} which is the desired lower bound for even integers. For odd and non-integer arguements, we first see that \begin{align*} \frac{d}{dx} \frac{x}{\log{x}} &= \frac{\log{x} - 1}{\log^2{x}} \ge 0 \end{align*} for all $x \ge e$. So $x/\log{x}$ is a non-decreasing for $x \ge e$. Hence, for $n \ge 2$ we have \begin{align*} \pi\left(2n - 1\right) = \pi\left( 2n \right) \ge \frac{\log{2}}{2} \frac{2n}{\log{2n}} \ge \frac{\log{2}}{2} \frac{2n - 1}{\log{(2n - 1)}} \end{align*} Now we have the bound for all integers $n \ge 2$. For the non-integer values $x \ge 2$, it is simple to see that $\lfloor x \rfloor \ge 2x/3$. Hence, \begin{align*} \pi(x) = \pi \left( \lfloor x \rfloor \right) \ge \frac{\log{2}}{2} \frac{\lfloor x \rfloor}{\log{\lfloor x \rfloor}} \ge \frac{\log{2}}{2} \frac{2x/3}{\log{x}} = \frac{\log{2}}{3} \frac{x}{\log{x}} \end{align*} Our bounds are \begin{align*} \frac{\log{2}}{3} \frac{x}{\log{x}} \le \pi(x) \le \left( 3 \log{4} + \frac{2}{\log{2}} \right) \frac{x}{\log{x}} \end{align*} The constants are $A \approx 0.23104906018$ and $B \approx 7.044273165$.